/*
环形链表的约瑟夫问题
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

示例1
输入：
5,2     
返回值：
3  

说明：
开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3     
*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
//用环形链表模拟解决
typedef struct ListNode ListNode;
ListNode* buyListNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
//创建环形链表
ListNode* createList(int n)
{
    ListNode* head = buyListNode(1);
    ListNode* tail = head;
    for(int i = 2; i <= n; i++)
    {
        tail->next = buyListNode(i);
        tail = tail->next;
    }
    tail->next = head;
    return tail; //返回tail防止prev为空
}
int ysf(int n, int m ) {
    // write code here
    ListNode* prev = createList(n);
    ListNode* head = prev->next;
    ListNode* pcur = head;

    int count = 1;
    while(pcur->next != pcur)
    {
        if(count == m){
            //删除当前节点
            prev->next = pcur->next;
            free(pcur);
            //删除节点之后，要让pcur走向新的节点，重置count
            pcur = prev->next;
            count = 1;
        }else{
            //pcur向后遍历
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}